class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> tmp(nums.begin(), nums.end());
        sort(tmp.begin(), tmp.end());
        int left = 1000000, right = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != tmp[i])
                left = min(left, i), right = max(right, i);
        }
        return max(0, right - left + 1);
    }
};
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int max_left = -1000000, min_right = 1000000, left = -1, right = -1,
            n = nums.size();
        for (int i = 0; i < n; i++) {
            if (max_left <= nums[i]) {
                max_left = nums[i];
            } else {
                right = i;
            }
            if (min_right >= nums[n - i - 1]) {
                min_right = nums[n - i - 1];
            } else {
                left = n - i - 1;
            }
        }
        cout << left << ' ' << right <<endl;
        return right == -1 ? 0 : right - left + 1;
    }
};
class Solution {
public:
    long long incremovableSubarrayCount(vector<int>& nums) {
        int n = nums.size();
        long long ans = 0;
        int i = 0;
        while (i < n - 1 && nums[i] < nums[i + 1])
            i++;
        if (i == n - 1)
            return (long long)n * (n + 1) / 2;
        ans += i + 2;
        for (int right = n - 1; right == n - 1 || nums[right] < nums[right + 1];
             right--) {
            while (i >= 0 && nums[i] >= nums[right])
                i--;
            ans += i + 2;
        }
        return ans;
    }
};
class Solution {
public:
	vector<int> recoverArray(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int left = 0, nn = nums.size(), n = nn / 2;
		for (int right = 1; right * 2 <= nn; right++) {
			int len = nums[right] - nums[left];
			if (len % 2 == 1 || len == 0) continue;
			vector<bool> vb(nn, false);
			vector<int> ret;
			auto fun = [&](int left, int right, auto& f) {
				while (vb[left] == true)
					left++;
				vb[left] = true;
				while (nums[right] < nums[left] + len)
				{
					right++;
					if (right == nn) return false;
				}
				if (nums[right] != nums[left] + len)
					return false;
				vb[right] = true;				// 相等
				ret.push_back(nums[left] + len / 2);
				if (right == nn - 1){
                    if(ret.size() != n)
                        return false;
                	return true;
                }
				else {
					return f(left + 1, right + 1, f);
				}
				};
			if (fun(left, right, fun)) {
				// cout << left << ' ' << right << endl;
				return ret;
			}
		}
		return { 1, 2, 3 };
	}
};